package com.mlh.binarytree.BFS;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/3/26 10:41
 * @DESCRIPTION
 */
// 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
// class Node {
//     public int val;
//     public Node left;
//     public Node right;
//     public Node next;
// }

// 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
// 这里的下一个右侧节点可以是同一层隔的很远距离的节点
// 初始状态下，所有 next 指针都被设置为 NULL。
public class Connect {
    public Node method1(Node root) {
        if (root == null) {
            return root;
        }
        Deque<Node> treeNodes = new LinkedList<>();
        treeNodes.add(root);
        while (!treeNodes.isEmpty()) {
            int len = treeNodes.size();
            while (len > 0) {
                Node node = treeNodes.poll();
                len--;
                if (len > 0) {
                    node.next = treeNodes.peek();
                }
                if (node.left != null) {
                    treeNodes.add(node.left);
                }
                if (node.right != null) {
                    treeNodes.add(node.right);
                }
            }
        }
        return root;
    }

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

}